
#ifndef Network_
#define Network_

#include "LinkedQueue.h"
#include "LinkedStack.h"


class Network {
  public:
    virtual int Begin( int i ) = 0;
    virtual int NextVertex( int i ) = 0;
    virtual void InitializePos() = 0;
    virtual void DeactivatePos() = 0;
    virtual int Vertices() const = 0;
    virtual int Edges() const = 0;

    void BFS( int v, int reach[], int label );
    void DFS( int v, int reach[], int label );
    bool FindPath( int v, int w, int &length, int path[] );
    bool Topological( int v[] );

  private:
    void dfs( int v, int reach[], int label );
    bool findPath( int v, int w, int &length,
                   int path[], int reach[] );
};



void Network::BFS( int v, int reach[], int label )
{
    LinkedQueue<int> Q;
    InitializePos();
    reach[v] = label;
    Q.Add( v );

    while ( !Q.IsEmpty() ) {
        int w;
        Q.Delete( w );

        int u = Begin( w );
        while ( u ) {
            if ( !reach[u] ) {
                Q.Add( u );
                reach[u] = label;
            }
            u = NextVertex( w );
         }
    }

    DeactivatePos();
}

void Network::DFS( int v, int reach[], int label )
{
    InitializePos();
    dfs( v, reach, label );
    DeactivatePos();
}

void Network::dfs( int v, int reach[], int label )
{
    reach[v] = label;
    int u = Begin( v );
    while (u) {
        if ( !reach[u] )
            dfs(u, reach, label);
        u = NextVertex( v );
    }
}

bool Network::FindPath( int v, int w, int &length, int path[] )
{
    // path[0:length]

    path[0] = v;
    length = 0;
    if ( v == w ) return true;

    int n = Vertices();
    InitializePos();
    int *reach = new int[n+1];
    for ( int i = 1; i <= n; i++ )
        reach[i] = 0;

    bool x = findPath( v, w, length, path, reach );

    DeactivatePos();
    delete [] reach;

    return x;
}

bool Network::findPath( int v, int w, int &length, int path[], int reach[] )
{
    reach[v] = 1;

    int u = Begin( v );
    while ( u ) {
        if ( !reach[u] ) {
            length++;
            path[length] = u;

            if ( u == w ) return true;
            if ( findPath( u, w, length, path, reach ) )
                return true;
            length--;
        }
        u = NextVertex(v);
    }

    return false;
}

bool Network::Topological( int v[] )
{
    // topo order in v[0:n-1]

    int i;
    int n = Vertices();
    int *InDegree = new int[n+1];
    InitializePos();

    for ( i = 1; i <= n; i++ )
        InDegree[i] = 0;
    for ( i = 1; i <= n; i++ ) {
        int u = Begin( i );
        while ( u ) {
            InDegree[u]++;
            u = NextVertex( i );
        }
    }

    LinkedStack<int> S;
    for ( i = 1; i <= n; i++ )
        if ( !InDegree[i] )
            S.Add(i);

    i = 0;
    while ( !S.IsEmpty() ) {
        int w;
        S.Delete( w );
        v[i++] = w;
        int u = Begin( w );
        while ( u ) {
            InDegree[u]--;
            if ( !InDegree[u] )
                S.Add( u );
            u = NextVertex(w);
        }
    }

    DeactivatePos();
    delete [] InDegree;

    return (i == n);
}

#endif

